package code1.binary_tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 前序、后序、中序遍历(统一迭代法)
 * 原题链接：
 * https://leetcode.cn/problems/binary-tree-preorder-traversal/
 * https://leetcode.cn/problems/binary-tree-postorder-traversal/
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/
 */
public class P144_3 {

    //核心思想：在把根(中间)节点加入栈中之后，再加入一个空节点，标记这个根节点还未处理过(还没有加入结果集中)

    //中序遍历(统一迭代法)
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode top = stack.pop();
            if(top!=null){                      //左根右，对应到栈里就是：右根左
                if(top.right!=null){
                    stack.push(top.right);      //往栈中添加右节点
                }
                stack.push(top);                //添加中节点
                stack.push(null);         //中节点尚未处理，加入空节点做为标记
                if(top.left!=null){
                    stack.push(top.left);       //添加左节点
                }
            }else{
                TreeNode cur = stack.pop();     //访问到空节点，说明下一个是中节点
                result.add(cur.val);
            }
        }
        return result;
    }

    //前序遍历(统一迭代法)
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode top = stack.pop();
            if(top!=null){                      //根左右，对应到栈里就是：右左根
                if(top.right!=null){
                    stack.push(top.right);      //往栈中添加右节点
                }
                if(top.left!=null){
                    stack.push(top.left);       //添加左节点
                }
                stack.push(top);                //添加中节点
                stack.push(null);         //中节点尚未处理，加入空节点做为标记
            }else{
                TreeNode cur = stack.pop();     //访问到空节点，说明下一个是中节点
                result.add(cur.val);
            }
        }
        return result;
    }

    //后序遍历(统一迭代法)
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode top = stack.pop();
            if(top!=null){                      //左右根，对应到栈里就是：根右左
                stack.push(top);                //添加中节点
                stack.push(null);         //中节点尚未处理，加入空节点做为标记
                if(top.right!=null){
                    stack.push(top.right);      //往栈中添加右节点
                }
                if(top.left!=null){
                    stack.push(top.left);       //添加左节点
                }
            }else{
                TreeNode cur = stack.pop();     //访问到空节点，说明下一个是中节点
                result.add(cur.val);
            }
        }
        return result;
    }
}
